package com.LeetCode.dp;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 最大矩形
 */
public class MaxMalRectangle {

    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int n = matrix.length;
        int m = matrix[0].length;
        int res = 0;
        int[][] dp = new int[n][m];

        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                dp[i][j] = matrix[i][j] == '0' ? 0 : dp[i > 0 ? i - 1 : 0 ][j] + matrix[i][j] -'0';
            }
        }

        for(int i = 0; i<n; i++){
            int[] tmp = dp[i];
            res = Math.max(res, findMaxRectangle(tmp));
        }

        return res;
    }

    public int findMaxRectangle(int[] heights){
        int[] tmp = new int[heights.length + 2];
        System.arraycopy(heights, 0 , tmp , 1,heights.length);

        //存的是坐标
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0;
        for(int i = 0; i<tmp.length; i++){
            while(!stack.isEmpty() && tmp[i] < tmp[stack.peek()]){
                int h = tmp[stack.pop()];
                res = Math.max((i - stack.peek() - 1) * h , res);
            }
            stack.push(i);
        }

        return res;
    }

    @Test
    public void test(){
        char[][] matrix = {
                {'1','0','1','0','0'},
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'1','0','0','1','0'},

        };
        char[][] matrix2 = {
                {'1','0'},
                {'0','1'}
        };
        System.out.println(maximalRectangle(matrix2));
//        System.out.println(findMaxRectangle(new int[]{1,0}));
    }
}
